package com.chen;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class day01 {
    public static void main(String[] args) {
        // 给定一个整数数组 nums 和一个整数目标值 target，
        // 请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        //你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
        // 1.使用连个for循环暴力搜索
        int[] nums = {2, 7, 11, 15};
        int target = 26;
        int[] ints = twoSum2(nums, target);
        System.out.println(Arrays.toString(ints));
    }


    /**
     * 寻找数组中两个数之和等于目标值的索引
     * 此方法使用双循环遍历数组中的每个元素，并与后面的元素相加，以查找满足条件的两个数
     * 当找到两个数的和等于目标值时，返回它们的索引
     * 如果没有找到这样的两个数，方法返回null
     * 这个方法不是最高效的解决方案，特别是对于大数组，因为它的时间复杂度为O(n^2)
     * 但它的实现简单直观，适用于理解两数之和问题的基本解决思路
     *
     * @param nums   输入的整数数组
     * @param target 目标值，我们需要找到数组中两个数的和等于这个值
     * @return 如果找到两个数的和等于目标值，返回包含这两个数索引的数组；如果没有找到，返回null
     */
    public static int[] twoSum(int[] nums, int target) {
        // 外层循环遍历数组的每个元素
        for (int i = 0; i < nums.length; i++) {
            // 内层循环从当前元素的下一个元素开始，遍历数组
            for (int j = i + 1; j < nums.length; j++) {
                // 检查当前两个元素的和是否等于目标值
                if (nums[i] + nums[j] == target) {
                    // 如果找到满足条件的两个数，返回它们的索引
                    return new int[]{i, j};
                }
            }
        }
        // 如果没有找到满足条件的两个数，返回null
        return null;
    }


    /**
     * 使用HashMap优化的两数之和解法
     * 该方法通过单次遍历数组，并利用HashMap存储和查找元素，提高了查找效率
     *
     * @param nums   输入的整数数组
     * @param target 目标值，即两数之和所应等于的值
     * @return 返回一个包含两个索引的数组，这两个索引指向的元素之和等于目标值；如果不存在这样的元素对，则返回null
     */
    public static int[] twoSum2(int[] nums, int target) {
        // 创建HashMap用于存储数组元素及其索引
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 检查目标值与当前元素的差值是否已存在于HashMap中
            if (map.containsKey(target - nums[i])) {
                // 如果存在，说明找到了满足条件的元素对，返回它们的索引
                return new int[]{map.get(target - nums[i]), i};
            }
            // 将当前元素及其索引存入HashMap中，以便后续查找
            map.put(nums[i], i);
        }
        // 如果遍历结束仍未找到满足条件的元素对，返回null
        return null;
    }
}
